// 螺旋矩阵
class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int>>& matrix) {
            int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
            int m = matrix.size(), n = matrix[0].size();
            vector<vector<bool>> used(m, vector<bool>(n));
            vector<int> res(m * n);
            int a = 0, b = 0, d = 1;
            for (int i = 0; i < m * n; i++)
            {
                used[a][b] = true;
                res[i] = matrix[a][b];
                int x = a + dx[d], y = b + dy[d];
                if (x < 0 || x == m || y < 0 || y == n || used[x][y])
                {
                    d = (d + 1) % 4;
                    x = a + dx[d], y = b + dy[d];
                }
                a = x, b = y;
            }
            return res;
        }
    };

// 旋转图像
class Solution {
    public:
        void rotate(vector<vector<int>>& matrix) {
            int m = matrix.size(), n = matrix[0].size();
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < i; j++)
                {
                    swap(matrix[i][j], matrix[j][i]);
                }
            }
            for (int i = 0; i < m; i++)
            {
                reverse(matrix[i].begin(), matrix[i].end());
            } 
        }
    };

// 搜索二维矩阵
class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            int m = matrix.size(), n = matrix[0].size();
            int x = 0, y = n - 1;
            while (x < m && y >= 0)
            {
                if (target < matrix[x][y]) y--;
                else if (target > matrix[x][y]) x++;
                else return true;
            }
            return false;
        }
    };